package pro.softzhang.algo.lc700;

import pro.softzhang.algo.flag.difficulty.DGreen;
import pro.softzhang.algo.flag.knowledge.KDynamicPlanning;
import pro.softzhang.algo.flag.theme.TStairs;
import pro.softzhang.algo.flag.x.XOptimal;

@DGreen
@KDynamicPlanning
@TStairs
public class LC746_MinCostClimbingStairs {
    public static void main(String[] args) {
        int[] cost = new int[]{10, 15, 20};
        int min = new Solution1().minCostClimbingStairs(cost);
        System.out.println(min);
    }

    /**
     *
     */
    static
    class Solution {
        public int minCostClimbingStairs(int[] cost) {
            int stairs = cost.length;
            int[] climbing = new int[stairs];
            climbing[0] = cost[0];
            climbing[1] = cost[1];
            for (int i = 2; i < stairs; i++) {
                climbing[i] = Math.min(climbing[i - 1], climbing[i - 2]) + cost[i];
            }
            return Math.min(climbing[stairs - 1], climbing[stairs - 2]);
        }
    }

    @XOptimal
    static
    class Solution1 {
        public int minCostClimbingStairs(int[] cost) {
            int[] dp = {cost[0], cost[1]};
            for (int i = 2; i < cost.length; i++)
                dp[i % 2] = Math.min(dp[0], dp[1]) + cost[i];
            return Math.min(dp[0], dp[1]);
        }
    }
}
